#include "delaunay.h"

#include <algorithm>
#include <limits>

#include <iostream>

#include "boost/foreach.hpp"
#define foreach BOOST_FOREACH

namespace Tut {

bool edge_compare(const Edge& _edge1, const Edge& _edge2) {
	if((_edge1.point1 == _edge2.point1) &&
		(_edge1.point2 == _edge2.point2))
			return true;
	return false;
}

bool vector_compare(const Vector& _vector1, const Vector& _vector2) {
	if(_vector1.y < _vector2.y)
		return true;
	else if(_vector1.y == _vector2.y)
		return true;
	else
		return false;
}

bool vector_compare_id(const Vector& _vector1, const Vector& _vector2) {
	if(_vector1.id == _vector2.id) 
		return true;
	return false;
}

Delaunay::Delaunay(std::vector<Vector> _points) : points(_points) { 
	std::sort(points.begin(), points.end());
}

std::vector<Vector> Delaunay::convex_hull(void) {
	std::vector<Vector> result;

	result.push_back(points[0]);
#ifdef DEBUG1
	std::cout << "Ponto adicionado: "  << std::endl;
	points[0].show();
#endif
	
	Vector test_vector = Vector(result[0].x+ 100,result[0].y+0.1) - result[0];
	Vector convex_hull_point;
	Vector last_convex_hull_point = result[0];
	std::vector<Vector>::iterator chosen;
	bool gambi = true;
	while(1) {
		double min_angle = std::numeric_limits<double>::infinity();
#ifdef DEBUG1
		std::cout << "Vetor de teste" << std::endl;
		test_vector.show();
#endif
		bool choose = false;
		for(std::vector<Vector>::iterator i = points.begin(); i != points.end(); i++ ) {
			if(last_convex_hull_point == result[0] && *i == result[0]) continue;
			Vector point = *i;
			Vector test = point - last_convex_hull_point;
			double angle = (test_vector.normalize()).angle(test.normalize());
#ifdef DEBUG1
			std::cout << "Ponto: "<< std::endl;
			point.show();
			std::cout << "Angulo : " << angle/M_PI*180.0 << std::endl;
#endif
			if(angle < 0.0) angle = (2.0*M_PI) + angle;
#ifdef DEBUG1
			std::cout << "Angulo : " << angle/M_PI*180.0 << std::endl;
			std::cout << "Angulo minimo : " << min_angle/M_PI*180.0 << std::endl;
#endif
			if(angle < min_angle) {
				min_angle = angle;
				convex_hull_point = point;
				chosen = i;
				choose = true;
			} else if(angle == min_angle) {
				if(convex_hull_point.length() < point.length()) {
					min_angle = angle;
					convex_hull_point = point;
					chosen = i;
					choose = true;
				}
			}
		}
		if(convex_hull_point == (result[0]) && !gambi) break;
		else {
#ifdef DEBUG1
			std::cout << "Resultado do tamanho: " << result.size() << std::endl;
#endif
			result.push_back(Vector(convex_hull_point));
			if(choose) points.erase(chosen);
			test_vector = convex_hull_point - last_convex_hull_point;
			last_convex_hull_point = convex_hull_point;
#ifdef DEBUG1
			std::cout << "Ponto escolhido: " << std::endl;
			convex_hull_point.show();
#endif
		}
		gambi = false;
#ifdef DEBUG1
		std::cout << "----------" << std::endl;
#endif
	}

	return result;
}

std::vector<Edge> Delaunay::triangulation(void) {
	std::vector<Edge> result;
	std::vector<Edge> free_edges;
	std::vector<Vector> convexhull = convex_hull();
	Edge first_edge(convexhull.at(0), convexhull.at(1));
	

	std::vector<Vector>::iterator already1;
	bool erase_already1 = false;
	std::vector<Vector>::iterator already2;
	bool erase_already2 = true;
	for(std::vector<Vector>::iterator i = points.begin(); i != points.end(); i++ ) {
		if(vector_compare_id(*i,convexhull.at(0))) {
			already1 = i;
			erase_already1 = true;
			std::cout << "Zela1" << std::endl;
		}
		if(vector_compare_id(*i,convexhull.at(1))) {
			already2 = i;
			erase_already2 = true;
			std::cout << "Zela2" << std::endl;
		}
	}
	if(erase_already1) points.erase(already1);
	//if(erase_already2) points.erase(already2);
	result.push_back(first_edge);
	double max_angle = -1.0;
	Edge last_edge = first_edge;
	std::vector<Vector>::iterator choosen;
	for(std::vector<Vector>::iterator i = points.begin(); i != points.end(); i++ ) {
		Vector point = *i;
		double angle = ((last_edge.point1 - point).normalize()).angle((last_edge.point2 - point).normalize());
		if(angle < 0.0) angle = (2.0*M_PI) + angle;
		if(angle > max_angle) {
			angle = max_angle;
			choosen = i;
		}
		
	}
	Edge new_edge2(last_edge.point1,*choosen);
	Edge new_edge1(last_edge.point2, *choosen);
	result.push_back(new_edge2);
	result.push_back(new_edge1);
	points.erase(choosen);

	std::cout << "Total result: " << result.size() << std::endl;
	return result;
}



}

